package algorithms;

import java.util.Arrays;

/**
 * 选择排序(Selection sort)是一种简单直观的排序算法。
 * 它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素，存放在序列的起始(末尾)位置，直到全部待排序的数据元素排完。
 */
public class SelectSort {

    public static void main(String[] args) {
        int[] arr = new int[]{7, 2, 4, 1, 6, 9, 8, 5};
        System.out.println(Arrays.toString(arr));
        selectSort2(arr);
        System.out.println(Arrays.toString(arr));
    }

    private static void selectSort(int[] arr) {
        int k = 1;
        for (int i = 0; i < arr.length; i++) {
            int min = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[min] > arr[j]) {
                    min = j;
                }
            }
            if (i != min) {
                int temp = arr[i];
                arr[i] = arr[min];
                arr[min] = temp;
            }
            System.out.println("第" + k + "次排序结果: " + Arrays.toString(arr));
            k++;
        }
    }

    private static void selectSort2(int[] arr) {
        for (int i = 0; i < arr.length; i++) {

            //最大值 下标
            int pos = 0;
            //最大值
            int max = 0;
            for (int j = 0; j < arr.length - i; j++) {
                if (arr[j] > max) {
                    max = arr[j];
                    pos = j;
                }
            }
            //把最大值max和arr最后一个未排序的交换位置
            int temp = arr[pos];
            arr[pos] = arr[arr.length - i - 1];
            arr[arr.length - i - 1] = temp;
        }
    }
}
